package leecode

func hIndex(citations []int) int {
	if len(citations) == 1 && citations[0] > 0 {
		return 1
	}
	n := len(citations)
	left := 0
	right := len(citations) - 1
	processH(citations, left, right)
	h := 0
	for i := n - 1; i >= 0; i-- {
		if citations[i] >= n-i {
			h = n - i
		} else {
			break
		}
	}
	return h
}

func processH(nums []int, left, right int) {
	if left == right {
		return
	}
	mid := (left + right) >> 1
	processH(nums, left, mid)
	processH(nums, mid+1, right)
	mergeH(nums, left, mid, right)
}

func mergeH(nums []int, left, mid, right int) {
	help := make([]int, right-left+1)
	i, p1, p2 := 0, left, mid+1
	for p1 <= mid && p2 <= right {
		if nums[p1] < nums[p2] {
			help[i] = nums[p1]
			i++
			p1++
		} else {
			help[i] = nums[p2]
			i++
			p2++
		}
	}
	//检测数组左侧是否还有未排序的元素
	for p1 <= mid {
		help[i] = nums[p1]
		p1++
		i++
	}
	//右侧
	for p2 <= right {
		help[i] = nums[p2]
		p2++
		i++
	}
	//将值赋值给nums数组
	for i := 0; i < len(help); i++ {
		nums[i+left] = help[i]
	}
}
